/** date:21-07-11
 *  The following program implements binary search  on a given array,to find the 
 *  position 
 */ 
// binsearch returns the p
def binSearchRecurse(xs:Array[Int],x:Int):Int={
    def binSearch1(low:Int,high:Int):Int ={
        if(low > high) -1 
        else{
            var m=(low+high)/2
            if(x==xs(m)) m
            else if(x<xs(m))  binSearch1(low,m-1)
            else binSearch1(m+1,high)
        }        
    }
    binSearch1(0,xs.length-1)
}


def iterBinSearch(findHere:Array[Int],target:Int):Int ={
    var i=0
    var j=findHere.length-1
    while(i<=j) {
        var mid=(i+j)/2
        if(findHere(mid)==target) return mid
        else if(findHere(mid)>target) j=mid-1
        else i=mid+1
    }
    -1   
} 

test("binary search works") {
    def bSearchTester(bSearch: (Array[Int],Int) => Int) = {
         bSearch(Array(),6) should equal(-1)
         bSearch(Array(57),56) should equal (-1)
         bSearch(Array(57),57) should equal (0)
         var a=Array[Int](6,18,24,32)
         for(elem<-a) {
             a(bSearch(a,elem)) should equal (elem)
         }
          //negative test cases
         bSearch(Array(6,18,24,32),3) should equal (-1)
         bSearch(Array(6,18,24,32),21) should equal (-1)
         bSearch(Array(6,18,24,32),37) should equal (-1)
    }
    
    bSearchTester(binSearchRecurse)
    bSearchTester(iterBinSearch)
}
//println(iterBinSearch(Array(2,3,5,6,56,78,90),5))


